A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source computing device to a destination computing device. The destination computing device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
Certain devices, referred to as routers, maintain routing information that describes routes through the network. A “route” can generally be defined as a path between two locations on the network. Upon receiving an incoming packet, the router examines information within the packet to identify the destination for the packet. Based on the destination, the router forwards the packet in accordance with the routing information.
Conventional routers often maintain the routing information in the form of one or more routing tables. The form and contents of the routing tables often depends on the routing algorithm implemented by the router. Common routing algorithms include distance vector routing algorithms and path vector routing algorithms. Many of these algorithms make use of the concept of a “hop,” which refers to a connection between two devices. Consequently, the distance between two devices is often measured in hops. Furthermore, in reference to routing a packet, the “next hop” from a network router typically refers to a neighboring device along a given route.
The physical connection between two devices on a network is generally referred to as a link. Many conventional computer networks, including the Internet, are designed to dynamically reroute data packets in the event of a topology change, such as a link failure. Upon a topology change, the routers transmit new connectivity information to neighboring devices, allowing each device to update its local routing information. Links can fail for any number of reasons, such as failure of the physical infrastructure between the devices, or failure of the devices interfacing with the link. The size and complexity of routing information maintained by routers within large networks can be significant. As a result, updating the routing information due to changes in network topology can consume considerable computing resources and substantially delay rerouting of packets.